package 回溯;

/**
 * 79. 单词搜索
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 * 思路： 采用回溯算法，对于每一个字母，都右上下左右四个方向，递归判断是否匹配，直到递归层数为word的长度，则返回true，否则返回false。
 *
 *  详细解题思路：
 *      1：问题分析：
 *          需要在二维网格中搜索是否存在给定单词；
 *          单词的每个字符必须要按照顺序相邻，并且不能重复使用同一个单元格；
 *      2：深度优先+回溯：
 *          从网格的每个单元格出发，尝试向四个方向(上下左右)进行搜索；
 *          如果找到当前字符匹配单词的相应字符，则继续递归搜索下一个字符；
 *          如果找到完整的单词，则返回true；
 *     3：剪枝优化：
 *          如果当前单元格的字符不匹配，直接返回false；
 *          使用回溯方法标记已使用的元素，避免重复使用；
 *
 */
public class L_79 {

    // 定义四个方向：上、右、下、左
    private int[] dx = {-1, 0, 1, 0};
    private int[] dy = {0, 1, 0, -1};

    public boolean exist(char[][] board, String word) {
        int row = board.length;
        if (row <= 0){
            return false;
        }
        int clo = board[0].length;
        // 二维数组中的每一个元素都可能作为起点
        for (int i = 0; i <row ; i++) {
            for (int j = 0; j < clo; j++) {
                if (dfs(board,word,0,i,j)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word,int u, int x, int y){
        // 如果当前字符不等于单词的当前字符，则返回false
        if (board[x][y] != word.charAt(u)){
            return false;
        }
        // 如果匹配到了最后一个字符，则返回true
        if (u == word.length() - 1){
            return true;
        }
        // 暂存当前字符，标记为已使用表示
        char tmp = board[x][y];
        board[x][y] = '.';

        // 向四个方向进行递归
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 检测是否越界,并且是未访问
            if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length && board[nx][ny] != '.'){
                if (dfs(board,word, u+1, nx, ny)){
                    return true;
                }
            }
        }

        // 回溯时恢复当前字符，表示当前字符未使用，便于下一次递归
        board[x][y] = tmp;
        return false;
    }
}
